//160. 相交链表

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p=headA;
        ListNode* q=headB;
        while(q!=p){
            p=p?p->next:headB;
            q=q?q->next:headA;
        }
        return p;
    }
};


//206. 反转链表

//方法一：迭代（双指针）
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur=head,*pre=nullptr;
        while(cur!=nullptr){
            ListNode*tmp=cur->next;//暂存后继节点cur.next
            cur->next=pre;//修改next引用指向
            pre=cur;//pre暂存cur
            cur=tmp;//cur访问下一节点
        }
        return pre;
    }
};


//234. 回文链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int>vals;
        while(head!=nullptr){
            vals.emplace_back(head->val);//将每个节点的值添加到 vals 向量中
            head=head->next;
        }
        //使用双指针法检查 vals 向量是否为回文。
        //i 指针从向量的开头开始，j 指针从向量的末尾开始
        for(int i=0,j=(int)vals.size()-1;i<j;++i,--j){
            if(vals[i]!=vals[j]){
                return false;
            }
        }
        return true;
    }
};


//141. 环形链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*>seen;
        while(head!=nullptr){
            if(seen.count(head)){
                return true;
            }
            seen.insert(head);//不存在则插入
            head=head->next;
        }
        return false;
        
    }
};


//21. 合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode*dum=new ListNode(0);//初始化伪头节点 dum,节点 cur指向dum  
        ListNode*cur=dum;  
        while(list1!=nullptr && list2!=nullptr){
            if(list1->val<list2->val){
                cur->next=list1;
                list1=list1->next;
            }
            else{
                 cur->next=list2;
                list2=list2->next;
            }
            cur=cur->next;
        }
         cur->next = list1 != nullptr ? list1 : list2;
         return dum->next;
    }
};



//2. 两数相加
//模拟
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
      ListNode *head=nullptr,*tail=nullptr;
      int carry=0;
      while(l1||l2){
        int n1=l1?l1->val:0;
        int n2=l2?l2->val:0;
        int sum=n1+n2+carry;
        if(!head){
            head=tail=new ListNode(sum%10);
        }else{
            tail->next=new ListNode(sum%10);
            tail=tail->next;
        }
        carry=sum/10;
        if(l1){
            l1=l1->next;
        }
        if(l2){
            l2=l2->next;
        }
      }  
      if(carry>0){
        tail->next=new ListNode(carry);
      }
      return head;
    }
};


//445. 两数相加 II
//反转链表+两数相加=秒杀

class Solution {
    ListNode* reverseList(ListNode* head) {
        ListNode *cur=head,*pre=nullptr;
        while(cur!=nullptr){
            ListNode*tmp=cur->next;//暂存后继节点cur.next
            cur->next=pre;//修改next引用指向
            pre=cur;//pre暂存cur
            cur=tmp;//cur访问下一节点
        }
        return pre;
    }
    ListNode* addTwo(ListNode* l1, ListNode* l2) {
      ListNode *head=nullptr,*tail=nullptr;
      int carry=0;
      while(l1||l2){
        int n1=l1?l1->val:0;
        int n2=l2?l2->val:0;
        int sum=n1+n2+carry;
        if(!head){
            head=tail=new ListNode(sum%10);
        }else{
            tail->next=new ListNode(sum%10);
            tail=tail->next;
        }
        carry=sum/10;
        if(l1){
            l1=l1->next;
        }
        if(l2){
            l2=l2->next;
        }
      }  
      if(carry>0){
        tail->next=new ListNode(carry);
      }
      return head;
    }
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1=reverseList(l1);
        l2=reverseList(l2);
        auto l3=addTwo(l1,l2);
        return reverseList(l3);
    }
};

//栈
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
       stack<int>s1,s2;
       while(l1){
        s1.push(l1->val);
        l1=l1->next;
       }
       while(l2){
        s2.push(l2->val);
        l2=l2->next;
       }
       
       int carry=0;
       ListNode*ans=nullptr;
       while(!s1.empty()||!s2.empty()||carry != 0){//s.empty()判断栈是否为空
       //carry != 0原因：当两个栈都为空时，意味着两个链表中的所有数字都已经处理完毕，但这并不代表加法运算就结束了，因为可能存在最后一个进位。
        int a=s1.empty() ? 0 : s1.top();
        int b=s2.empty() ? 0 : s2.top();
        int sum=a+b+carry;
        carry=sum/10;
        if(!s1.empty()) s1.pop();
        if(!s2.empty()) s2.pop();
        sum%=10;
        auto curnode=new ListNode(sum);
        curnode->next=ans;
        ans=curnode;//头节点指向新节点
       }
         
      return ans;

    }
};


// 19. 删除链表的倒数第 N 个结点
//双指针
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead=new ListNode(0);
        //设置虚拟节点 dummyHead 指向 head
        dummyHead->next=head;

        ListNode*p=dummyHead;
        ListNode*q=dummyHead;
        for(int i=0;i<n+1;i++){
            q=q->next;
        }

        while(q){
            p=p->next;
            q=q->next;
        }

        ListNode*delNode=p->next;
        p->next=delNode->next;
        delete delNode;

        ListNode*retNode=dummyHead->next;//删除虚拟节点
        delete dummyHead;

        return retNode;
    }
};




